package algorithm.dynamic;

/**
 * leetcode : https://leetcode.com/problems/jump-game/description/
 * Diffculty: Medium
 *
 * 很简单的动态规划问题。
 * @Author Antony
 * @Since 2018/7/2 18:50
 */
public class JumpGame {

    public static void main(String[] args) {
        int[] arr_1 = new int[]{2,3,1,1,4};
        int[] arr_2 = new int[]{3,2,1,0,4};

        System.out.println(canJump(arr_1));
        System.out.println(canJump(arr_2));
    }


    /**
     * maxJump 代表在这个点之前，最大可以跳的格子数。
     * 如果maxJump<=0 则代表不能跳到这个格子，直接返回false
     * maxJump>0 代表能跳到这个格子，则maxJump-1; 并且和当前格子的可跳跃数量比较。取最大的当做maxJump。
     * 能全部走完循环，则返回true
     */
    public static boolean canJump(int[] nums) {
        int maxJump = nums[0];
        for(int i=1; i<nums.length; i++){
            if(maxJump-- <= 0){
                return false;
            }
            maxJump = maxJump > nums[i] ? maxJump : nums[i];
        }
        return true;
    }
}
